The present invention relates to automatic generation of multi-terminal nets for a package such as a semiconductor chip package, and more particularly to a technique for automatically generating multi-terminal nets formed with one stroke so that those nets can be wired in a single-chip package without any redundant route.
Chip package parts represented by CPUs and ASICs have been enhanced significantly in both speed and packing density due to the progress of packaging techniques. The packaging is one of elementary techniques for effectively making electronic devices higher in performance and smaller in size in recent years. Under such circumstances, a high-performance automatic design system is an indispensable tool in product development fields now that products are getting diversified more and more and their life cycles are becoming shorter and shorter.
Wiring in a chip package is one of such automatic designs. This wiring is divided into two types; net wiring that derives each wiring route according to predetermined connection directive information (net(s)) and net generation that derives each wiring route while generating the connection directive information which can be wired. The present invention is applied to the latter wiring process.
Generally, wiring in a package is done radially from a terminal (bonding pad) group disposed at a bear chip (chip body) side located in the center toward a pin group (or interlayer connecting parts referred to as vias) arrayed at the outer periphery. Its wiring pattern should satisfy the following conditions.
E It should be connectable.
E The total wiring length should be as short as possible.
E It should satisfy the design rules (wiring pitch, gap between the pattern and part, etc.).
ENo redundant wiring route is allowed.
There is a known technique for implementing the package wiring described above which is referred to as two-terminal net generation algorithm. According to this technique, objects to be wired are divided into two terminal groups (source and sink). A given element in one group is connected to a given element in the other group temporarily by a shortest route searching method such as Dijkstra method, and any intersection of the generated routes is eliminated so as to finally generate nets which can be wired for all objects to be connected. For example, Japanese Patent 2938431 discloses a technique in which design information that indicates pad arrangement on a chip, pin arrangement on a package, correspondence of pads and pins, etc. is read and analyzed to create a wiring problem, pads and pins are classified into source elements and sink elements, the same ID numbers are consecutively assigned to pads and pins interconnected with each other, imaginary triangles having source/sink elements as vertexes are generated by applying the Delaunay""s triangulation method to the source and sink elements, the pins are then classified into some levels by using those triangles, it is determined whether or not each side of the triangles crosses a wiring, a wiring route is derived by connecting the sides determined to be crossed, and the result of the wiring design is output.
Japanese Published Unexamined Patent Application 11-296560 discloses another technique in which design information is read and analyzed to create a wiring problem just like the technique disclosed in the above Japanese patent, bonding pads and pins of a semiconductor package are associated with each other, a monitoring side used to monitor a wiring route is created between a given sink element and a wiring inhibited area, a wiring route is searched by, for example, the Dijkstra method in a manner that crossing is allowed, an evaluation value is calculated by weighting the length of a candidate route with a coefficient if it crosses a monitoring side, a candidate route having the lowest evaluation value is selected as a partial route, and the result of wiring is finally output.
As described above, generally, wiring in a single-chip package is done radially from wire bonding pads disposed around a bear chip located in the center of the substrate toward pin parts (including vias) disposed along the outer periphery. The above-described two-terminal net generation algorithm classifies the objects to be connected into a wire bonding pad group (source) and a pin part group (sink) before wiring is done. When designing an actual chip package, however, it is often required to extend a wiring route from a source toward a sink and further to a plated terminal positioned at the outer periphery of the package for some reason of the chip fabrication. In case an attempt is made to automate all the processings up to this extension (to generate three- or more-terminal nets automatically), many problems that are difficult to be solved are expected to arise even when the present combination of the shortest route searching and crossing elimination methods is further expanded. The problems expected would be frequent occurrence of route searching operations depending on objects for intersecting routes (resulting in longer processing time), no assurance of obtaining a solution for connection, etc. Consequently, designers in the field are requested to lay most of lead wires up to these plated terminals manually.
Referring to a simple example shown in FIG. 1, symbols A to F denote parts such as pins or the like disposed between an output terminal (pad) group and an input terminal (plated terminal) group. Arrows lines 1 to 6 denote routes from the output terminal group to the input terminal group via those parts. In case a three-terminal net is configured by automatically generating a two-terminal net simply twice, a route passing through the part D could not be obtained (a net could not be generated) if the wiring capacity between 0the parts C and F is 100%. In that case, all the nets between the parts C and F must be reviewed and modified to wirable nets which would, however, lead to problems such as definition of an optimum net modification method, necessity for route searching, control of, generation of redundant circuitry (detour), and route evaluation. Further, after the net modification, wiring with nets is done in which the solution for connection could not be assured without enough examination of the nets, and the processing is repeated while checking the solution for connection, leading to the conclusion that the processing could be finished more quickly by manual work from the beginning. Of course, the manual work would impose a burden on the designer.
Accordingly, it is an object of the present invention to derive wirable multi-terminal nets including no redundant route quickly without route searching.
It is another object of the present invention to provide an automatic multi-terminal net generation method for deriving the multi-terminal nets quickly.
It is still another object of the present invention to provide an automatic multi-terminal net generation apparatus for deriving the multi-terminal nets quickly.
It is still another object of the present invention to provide a program storage medium for storing a program used to perform the above automatic multi-terminal net generation method for deriving the multi-terminal nets quickly.
According to the present invention, when N-terminal nets (N is equal to or greater than three) are generated automatically, (Nxe2x88x921)-terminal connection data satisfying a given design rule for a package are input as initial data, and then a two-terminal net generation processing is performed for a group of terminals corresponding to start points of wiring and a group of N-th terminals for which nets are to be generated, with any intermediate terminal group being ignored. Then, provisional nets are generated by combining the initial data with the result of the two-terminal net generation, and these provisional nets are modified to satisfy the design rule for the package. The N-terminal nets are thereby generated automatically. In case the above (Nxe2x88x921) is equal to or greater than three, the connection data to be input as initial data must be generated according to the present invention.
Consequently, the first aspect of the present invention is a method for automatically generating multi-terminal nets, in which said nets are generated sequentially from wiring start terminals toward end terminals in a package including a plurality of terminal groups, said method comprising the steps of:
(a) inputting, as initial data, connection data between a first terminal group including said wiring start terminals and a second terminal group next thereto;
(b) performing two terminal net generation for said first terminal group and a third terminal group positioned next to said second terminal group in which said second terminal group is ignored;
(c) generating provisional nets by combining said initial data with the result of said two-terminal net generation; and
(d) modifying said provisional nets so as to satisfy a design rule for said package;
wherein said steps (b) to (d) are repeated for fourth and succeeding terminal groups by inputting, as said initial data, the provisional nets modified in said step (d) if the multi-terminal nets are four- or more-terminal nets.
The second aspect of the present invention is an apparatus for automatically generating multi-terminal nets in which said nets are generated sequentially from wiring start terminals toward end terminals in a package including a plurality of terminal groups, said apparatus comprising:
(a) means for inputting, as initial data, connection data between a first terminal group including said wiring start terminals and a second terminal group next thereto;
(b) means for performing two-terminal net generation for said first terminal group and a third terminal group positioned next to said second terminal group in which said second terminal group is ignored;
(c) means for generating provisional nets by combining said initial data with the result of said two-terminal net generation; and
(d) means for modifying said provisional nets so as to satisfy a design rule for said package;
wherein the tow-terminal net generation by said means (b), the generation of the provisional nets by said means (c) and the modification of the provisional nets by said means (d) are repeatedly performed for fourth and succeeding terminal groups by inputting, as said initial data, the provisional nets modified by said means (d) if the multi-terminal nets are four- or more-terminal nets.
The third aspect of the present invention is a program storage medium that stores a program for performing the method for automatically generating multi-terminal nets according to the first aspect.